1. Field of the Invention
The present invention relates to database processing. More particularly, the present invention relates to a method for improving the processing speed of database instructions using a page prefetch cache.
2. The Background Art
One of the primary functions a computer is required to perform is that of processing information present in databases. When the database is large, it is necessary to have the processing function perform as efficiently as possible, or valuable time and computer resources may be wasted.
Database applications spend a significant fraction of time waiting on data stream cache misses. It is well known that cache misses contribute to a significant fraction of cycles per instruction (CPI) on database workloads. Many of these cache misses are due to accessing database data structures called xe2x80x9cpagesxe2x80x9d.
Database engines store data records in physical memory and on a hard disk in the form of pages. Each page holds several data or index records. The page size is typically in the range 2 kilobytes (KB) to 8 KB. The total amount of data that databases maintain in pages is large, e.g. gigabytes. Accessing pages within the database has a propensity to cause compulsory or capacity cache misses.
The end result of these cache misses is that they cause delays in processing an instruction. If data required to process the instruction is not available in data cache memory, valuable central processing unit (CPU) cycles are wasted while the required data is retrieved from external memory, a process which can often take up to 100 or more CPU cycles. During these CPU cycles, the CPU is either executing instructions which cause the data to be retrieved, or is waiting for the required data to be present in the data cache.
It would therefore be beneficial to provide an apparatus and method for ensuring that data required for the execution of an instruction is present in a data cache memory or other memory storage close to the pipeline prior to that data being required for the execution of an instruction.
The present invention comprises an apparatus for reducing the impact of cache misses using a page prefetch cache. The page prefetch cache resides on a CPU chip or in an adjacent off-chip architecture. The page prefetch cache has space to store xe2x80x9cnxe2x80x9d complete database pages in which the database page size varies but is typically in the range of 2 KB to 8 KB where typically xe2x80x9cnxe2x80x9d is a small number. By way of example and not of limitation, the number of database pages stored by the page prefetch cache is four.
In operation, during a database application, the page prefetch cache is enabled. The CPU issues a page prefetch instruction to load pages into the page prefetch cache. For optimal benefit the database page needs to be loaded into the page prefetch cache prior to the first use of the database page. All load instructions check the page prefetch cache. If the requested database page is in the page prefetch cache, access to that data page do not slow the CPU or are returned to the pipeline much faster.
Numerous means for generating page prefetch instructions can be employed. By way of example, the means for generating a page prefetch instruction include a compiler or developer software. The compiler or developer software identifies locations in the code where access to a particular database page will start. Locations are identified through a profile feedback or through a plurality of xe2x80x9cpragmasxe2x80x9d inserted in the source code by the developers. The compiler inserts the new page prefetch instruction at the designated locations defined by the profile feedback or pragmas. The newly inserted page prefetch instructions bring the page to be accessed into the page prefetch cache. When the page prefetch instruction is executed, the entire page is received by the page prefetch cache. Subsequent load instructions that access the page prefetch cache return the prefetched database pages to a pipeline significantly faster.
The present invention provides a method for reducing cache misses and improving performance. The method provides for the issuance of pre-fetch commands which store one or more database pages in the page prefetch cache before each of the database pages must be accessed. Simultaneously, as database page prefetch commands are issued, the method determines whether the page prefetch cache has a free entry for a new database page.